package com.yc.dataStructure;

import java.util.Random;

/**
 * 跳表结构
 * @author yuancan
 *
 * @param <T>
 */
public class SkipList<T extends Comparable<T>> {

	/** 链表头 */
	private Node<T> linkHead;

	//节点类型
	/** 节点类型：最小节点 */
	private final Integer NODE_TYPE_MIN = -1;
	/** 节点类型：最大节点 */
	private final Integer NODE_TYPE_MAX = 1;
	/** 节点类型：普通数据节点 */
	private final Integer NODE_TYPE_NORMAL = 0;

	/** 跳表最大层数 */
	private int maxLevel = 1;
	/** 有效节点数 */
	private int useableNodeNum = 0;
	/** 总节点数 */
	private int totalNodeNum = 2;

	/**
	 * 本链表会创建成如下形式
	 * MIN ————— 2  ———————————— 6 - MAX
	 *  |        |               |    |
	 * MIN ————— 2 ————— 4 ————— 6 - MAX
	 *  |        |       |       |    |
	 * MIN - 1 - 2 - 3 - 4 - 5 - 6 - MAX
	 *
	 * 除了普通数据节点，还有MIN 和 MAX，作为两边的边界节点
	 * 初始化的时候会创建  MIN - MAX 两个初始节点链表
	 */
	public SkipList() {
		//创建尾节点
		Node<T> tailNode = new Node(null, null, null, NODE_TYPE_MAX, 1);
		//创建头节点
		linkHead = new Node(null, tailNode, null, NODE_TYPE_MIN, 1);
		System.out.println("---init SkipList over--");
	}

	//增加节点
	public boolean add(T value) {
		//查找是否有
		if (find(value)) {
			return false;//已有元素，插入失败
		}
		int level = getLevel();//新增节点层数
		if (level > maxLevel)
			maxLevel = level;
//		System.out.println(value + " : " + level);
		Node<T> topNewNode = addCurrent(value, linkHead, level);
		//判断是否需要在当前层数基础上继续往上加
		if (level > topNewNode.getLevel()) {//层数还不够
			for (int i = topNewNode.getLevel()+1; i < level+1; i++) {
				//寻找当前最大层到最大节点
				Node<T> topMaxNode = findMaxNode(topNewNode);
				//加最大节点MAX
				Node<T> newMaxNode = new Node<T>(null, null, topMaxNode, NODE_TYPE_MAX, i);
				//加新节点
				Node<T> newNode = new Node<T>(topNewNode.getValue(), newMaxNode, topNewNode,NODE_TYPE_NORMAL, i);
				//加最小节点MIN
				Node<T> newMinNode = new Node<T>(null, newNode, linkHead, NODE_TYPE_MIN, i);

				//增加总节点数
				totalNodeNum += 3;
				//修改最新头节点以及最新最上面的普通节点
				linkHead = newMinNode;
				topNewNode = newNode;
			}
		}
		useableNodeNum++;
		return true;
	}

	/**
	 * 寻找该节点当前层的最大节点
	 * @param currentNode
	 * @return
	 */
	private Node<T> findMaxNode(Node currentNode) {
		while (true) {
			if (null != currentNode.getRightNode()) {
				currentNode = currentNode.getRightNode();
			} else {
				return currentNode;
			}
		}
	}

	/**
	 * 从当前节点currentNode开始遍历寻找位置插入新节点
	 * @param value			新插入的节点元素值
	 * @param currentNode	当前节点
	 * @param level			新插入的节点总共层数
	 * @return				新插入的节点最上层的那个节点
	 */
	private Node<T> addCurrent(T value, Node<T> currentNode, int level) {
		//遍历从当前节点到最后到所有该层节点
		for (; currentNode != null; currentNode = currentNode.getRightNode()) {
			Node<T> newNode = new Node<T>(value, currentNode.getRightNode(), null, NODE_TYPE_NORMAL, currentNode.getLevel());
			if (newNode.compareTo(currentNode) > 0 && newNode.compareTo(currentNode.getRightNode()) < 0) {
				Node<T> belowNewNode = addCurrent(value, currentNode.getBelowNode(), level);//下层
				//添加节点
				if (currentNode.getLevel() <= level) {//只要当前层数在要求的层数范围内，就新增
					newNode.setBelowNode(belowNewNode);
					currentNode.setRightNode(newNode);
					totalNodeNum++;
					return newNode;
				} else {//如果本层不增加，那么直接把底层新增的节点返回（有可能底层返回的是底层的底层节点）
					return belowNewNode;
				}

			}
		}
		return null;
	}


	/**
	 * 获取随机层数
	 * @return
	 */
	private int getLevel() {
		int level = 1;//第一层是每个元素必须有的
		Random r = new Random();//注意不要写成new Random(xxx)，否则就失去随机性里
		while(r.nextBoolean()) {
			level++;
		}
		return level;
	}


	/**
	 * 在跳表中是否能找到元素值
	 * @param value		要找的元素值
	 * @return	true 有该元素  false 无该元素
	 */
	public boolean find(T value) {
		//造一个假node作为查询参数，这里的层数1是随便写的，查找过程中用不到
		Node<T> findNode = new Node<>(value, null, null, NODE_TYPE_NORMAL, 1);
		findNode = findCurrent(findNode, linkHead);
		return (null != findNode);
	}

	/**
	 * 从某个节点开始迭代遍历 寻找节点node
	 * @param node			要查找的节点（该节点里必须有值value，节点类型nodeType）
	 * @param currentNode	查找的起始节点
	 * @return				找到的节点
	 */
	private Node<T> findCurrent(Node node, Node<T> currentNode) {
		//遍历从当前节点到最后到所有该层节点
		boolean findIn = false;//是否需要继续往下层寻找
		for (; currentNode != null; currentNode = currentNode.getRightNode()) {
			if (node.compareTo(currentNode) == 0) {
				return currentNode;//找到了，就不再循环
			} else if (node.compareTo(currentNode) > 0 && node.compareTo(currentNode.getRightNode()) < 0) {
				//本层没有该值，但在这个范围内：向下继续找
				findIn = true;
				break;
			} else {
				continue;
			}
		}

		if (findIn) {
			return findCurrent(node, currentNode.getBelowNode());
		} else {
			return null;//循环完该层，也没找到（某个范围都没找到） 遍历 迭代都结束
		}
	}




	/**
	 * 最大层数
	 * @return
	 */
	public int getMaxLevel() {
		return maxLevel;
	}

	/**
	 * 实际有用节点数
	 * @return
	 */
	private int getUseableNodeNum() {
		return useableNodeNum;
	}

	/**
	 * 总节点数
	 * @return
	 */
	private int getTotalNodeNum() {
		return totalNodeNum;
	}

	/**
	 * 链表节点
	 * @param <T> 节点的元素值value必须是可比较大小的（实现Comparable接口）
	 */
	class Node<T extends Comparable> implements Comparable<Node> {
		private T value;//存储值
		private Node<T> rightNode;//右边的节点   当为null时，表示最右边的最大节点
		private Node<T> belowNode;//下面并列的同一个节点，当为null时，表示最下边的节点
		private Integer nodeType;//-1: 最小节点    1： 最大节点   其他: 普通节点
		private Integer level;//层数
		public Node() {
			super();
		}
		public Node(T value, Node<T> rightNode, Node<T> belowNode, Integer nodeType, Integer level) {
			super();
			this.value = value;
			this.rightNode = rightNode;
			this.belowNode = belowNode;
			this.nodeType = nodeType;
			this.level = level;
		}
		public T getValue() {
			return value;
		}
		public void setValue(T value) {
			this.value = value;
		}
		public Node<T> getRightNode() {
			return rightNode;
		}
		public void setRightNode(Node<T> rightNode) {
			this.rightNode = rightNode;
		}
		public Node<T> getBelowNode() {
			return belowNode;
		}
		public void setBelowNode(Node<T> belowNode) {
			this.belowNode = belowNode;
		}
		public Integer getNodeType() {
			return nodeType;
		}
		public void setNodeType(Integer nodeType) {
			this.nodeType = nodeType;
		}
		public Integer getLevel() {
			return level;
		}
		public void setLevel(Integer level) {
			this.level = level;
		}

		@Override
		public String toString() {
			if (NODE_TYPE_MIN == nodeType) {
				return "MIN";
			} else if (NODE_TYPE_NORMAL == nodeType) {
				if (null != value) {
					return value.toString();
				} else {
					return "null";
				}
			} else if (NODE_TYPE_MAX == nodeType) {
				return "MAX";
			} else {
				return "unDefinition";
			}
		}

		@Override
		public int compareTo(Node o) {
			if (!Integer.valueOf(0).equals(nodeType) || !Integer.valueOf(0).equals(o.getNodeType())) {//两个节点中有边界节点
				if (nodeType == o.getNodeType()) {//类型相同，就相同
					return 0;
				} else {//两者类型不同
					if (NODE_TYPE_MIN == nodeType || NODE_TYPE_MAX == o.getNodeType()) {
						return -1;
					} else {
						return 1;
					}
				}
			} else {//正常的普通节点之间的比较
				return value.compareTo(o.getValue());
			}
		}
	}

//-----------------------------------辅助测试方法----------------------------------------------

	/**
	 * 打印跳表(可以比较直观的看一下生成的跳表的大致样子。因为不太好对齐，所以和实际的样子有差距)
	 */
	private void printSkipTable() {
		Node<T> leftNode = linkHead;
		Node<T> currentNode = leftNode;

		for (; leftNode != null; leftNode = leftNode.getBelowNode()) {
			for (currentNode = leftNode; currentNode != null; currentNode = currentNode.getRightNode()) {
				System.out.print(" - " + currentNode.toString());
			}
			System.out.println();//换行
		}
	}

	/**
	 * 在跳表中是否能找到元素值[和find功能一样，只是多了打印日志]
	 * @param value		要找的元素值
	 * @return	true 有该元素  false 无该元素
	 */
	private boolean find_show_log(T value) {
		//造一个假node作为查询参数，这里的层数1是随便写的，查找过程中用不到
		Node<T> findNode = new Node<>(value, null, null, NODE_TYPE_NORMAL, 1);
		findNode = findCurrent_show_log(findNode, linkHead);
		return (null != findNode);
	}

	/**
	 * 从某个节点开始迭代遍历 寻找节点node[和findCurrent功能一样，只是多了打印日志]
	 * @param node			要查找的节点（该节点里必须有值value，节点类型nodeType）
	 * @param currentNode	查找的起始节点
	 * @return				找到的节点
	 */
	private Node<T> findCurrent_show_log(Node node, Node<T> currentNode) {
		//遍历从当前节点到最后到所有该层节点
		boolean findIn = false;//是否需要继续往下层寻找
		for (; currentNode != null; currentNode = currentNode.getRightNode()) {
			if (node.compareTo(currentNode) == 0) {
				System.out.println(currentNode.getValue() + "： 找到了！");
				return currentNode;//找到了，就不再循环
			} else if (node.compareTo(currentNode) > 0 && node.compareTo(currentNode.getRightNode()) < 0) {
				//本层没有该值，但在这个范围内：向下继续找
				System.out.println(currentNode.getValue() + ": 向下层继续找...");
				findIn = true;
				break;
			} else {
				System.out.println(currentNode.getValue() + ": 下一个");
				continue;
			}

		}

		if (findIn) {
			return findCurrent_show_log(node, currentNode.getBelowNode());
		} else {
			return null;//循环完该层，也没找到（某个范围都没找到） 遍历 迭代都结束
		}
	}

	/**
	 * 初始化测试数据
	 */
	private void initTestData(SkipList<String> stringSkipList, int itemNum) {
		for (int i = 0; i < itemNum; i++) {
			stringSkipList.add(i + "");
		}
		System.out.println("添加数据完毕,最大层数:" + maxLevel + "， 实际有用节点数：" + useableNodeNum + ", 总节点数：" + totalNodeNum);
	}

	/**
	 * 性能测试
	 * 结论：五百万数据需要大概消耗一千万的空间，大概22层，但因为这些节点里其实只是"引用"，所以如果实际存储的数据比较大，这点消耗还是很划算的
	 * 查找时间：基本可以忽略
	 */
	private void performanceTest(SkipList<String> stringSkipList, int itemNum) {
		initTestData(stringSkipList, itemNum);
		//测试从中查询一个数的时间
		long startTime = System.currentTimeMillis();
		System.out.println(stringSkipList.find_show_log(899990 + ""));
		System.out.println(itemNum + "个元素中查找总共耗时" + (System.currentTimeMillis() - startTime) + "毫秒");
	}
	
	public static void main(String[] args) {
		//这里的范型使用里String，因为String也是实现Comparable接口的。也可以自定义实现了Comparable接口的类型
		SkipList<String> stringSkipList = new SkipList<String>();
		//添加节点
//		stringSkipList.add("d");
//		stringSkipList.add("a");
//		stringSkipList.add("c");
//		stringSkipList.add("b");
//		//打印跳表
//		stringSkipList.printSkipTable();

		//测试搜索一个5000000大小的跳表需要多长时间
//		stringSkipList.performanceTest(stringSkipList, 5000000);

		stringSkipList.initTestData(stringSkipList, 100);
		stringSkipList.printSkipTable();

	}

}
